#pragma once

#include <iostream>
#include <vector>
#include <bitset>
#include <string> // to_string
using namespace std;

struct HashBKDR
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}

		return val;
	}
};

struct HashAP
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct HashDJB
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}

		return hash;
	}
};

template<size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter // N表示准备要映射N个值
{
public:
	void Set(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N); // 注意优先级问题，在最后加括号
		size_t hash2 = Hash2()(key) % (_ratio * N);
		size_t hash3 = Hash3()(key) % (_ratio * N);

		_bits->set(hash1);
		_bits->set(hash2);
		_bits->set(hash3);

	}

	bool Test(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		if (!_bits->test(hash1))
		{
			return false; // 准确的
		}

		size_t hash2 = Hash2()(key) % (_ratio * N);
		if (!_bits->test(hash2))
		{
			return false; // 准确的
		}

		size_t hash3 = Hash3()(key) % (_ratio * N);
		if (!_bits->test(hash3))
		{
			return false;  // 准确的
		}

		return true; // 可能存在误判
	}

	// 一般不支持删除，因为可能会影响其它值（引用计数可以解决，但空间消耗更多了）
	//void Reset(const K& key);

protected:
	const static size_t _ratio = 5; // 根公式算出来，此时哈希函数是3个，所以m = 3n/ln2 约等于4.2 取5
	std::bitset<_ratio* N>* _bits = new std::bitset<_ratio * N>;
	// 库里的bit是放在栈上的，容易栈溢出，所以自己放到堆上（很挫）用自己写的就是放在堆上的
};